package sort;

public class BucketSort {
	public static long Sort(int[] list){
		long startTime = System.currentTimeMillis();
		
		//Finding the maximum number in list
		int maxNum=0, noOfBuckets = list.length>>10;
		for(int i=0; i<list.length; i++)
			if(maxNum < list[i]) maxNum = list[i];

		int bucketSize = ++maxNum/noOfBuckets;
		int[][] arrayOfArrays = new int[++noOfBuckets+1][bucketSize<<1];
		
		//Adding to buckets
		for(int i=0; i<list.length; i++){
			int bucket = list[i]/bucketSize, pos = arrayOfArrays[noOfBuckets][bucket]++;
			arrayOfArrays[bucket][pos] = list[i]; 
		}
		
		for(int i=0; i<noOfBuckets; i++){
			//Sorting buckets with Bubble sort
			for(int j=0; j<arrayOfArrays[noOfBuckets][i]; j++){
				for(int k=j+1; k<arrayOfArrays[noOfBuckets][i]; k++){
					if(arrayOfArrays[i][j] > arrayOfArrays[i][k]){
						int temp = arrayOfArrays[i][j];
						arrayOfArrays[i][j] = arrayOfArrays[i][k];
						arrayOfArrays[i][k] = temp;
					}
				}
			}
		}
		
		//Putting the buckets back into list
		int k=0;
		for(int i=0; i<noOfBuckets; i++){
			for(int j=0;  j<arrayOfArrays[noOfBuckets][i]; j++){
				list[k] = arrayOfArrays[i][j];
				k++;
			}
		}
		
		return System.currentTimeMillis()-startTime;
	}
}
